예전에 분명히 블로그에 기록해뒀는데 찾아도 안 나온다 -_-;
그래서 다시 기록.
https://github.com/WojciechMula/pyahocorasick/
원단 코드부는 c로 되어 있어 빠르다.
인덱스를 부여해서 탐색된 인덱스를 얻을 수 있다.
인덱스가 겹치면 최후에 사용한 인덱스만 유효하므로 사전에 매핑이 필요하다.
시스템에 모듈 지원 문제가 있다면 .so만 복사해서 사용해도 된다. 이 때 .so를 실행 경로에 위치시키고 해당 경로를 파이썬 패쓰에 추가해야 한다. 런타임에서 패쓰 추가가 가능하다. 물론 아키가 맞아야 한다. x86 빌드하고 arm에서 쓸 수 없다.
cPickle을 이용하여 일괄 패키징해서 사용해도 된다. 임포트에서 자유롭다.
당연히 아호코라식이므로 어마무시한 속도가 나온다. pypy로 돌리면 문자열 관련 부가 작업에서 시간을 더 벌 수 있는데 여건이 될 수도 안 될 수도 있다.
문자열 탐색 관련 이것저것 짜기도 많이 짜봤는데, 원할한 팀웤을 위해서 C로 짤 수가 없다.
예전 시도로 GPU - CUDA를 시행한 적도 있다. 문제는 CUDA의 멀티코어에 적합한 알고리즘이 아니다. 아호코라식은 트리를 선형으로 뽑아가는데 멀티코어로 짜려면 그냥 데이터를 나눠서 분할정복하는 방식만 유효하다. 스리랑카인가 파키스탄에서 GPU용 아호코라식 논문을 쓴 걸 본 적이 있다. 내 블로그 어딘가 기록해 둔 것이 있을 듯. 여튼 제목과는 달리 아호코라식이 아니다. 백트레이싱 없이 걍 트리 탐색만 하는 것.
분할 정복으로 멀티코어 프로그래밍을 하면 데이터 덤핑 성능과의 프로파일링 전투가 된다. SSD에서 메인메모리로 덤핑, 메인메모리에서 GPU로 덤핑, CUDA 다 까먹었는데 CUDA한테 메모리 공유를 맡기는 방법, mmap으로 사상시켜서 등등 한 적이 있는 것 같다. 사실 기억 잘 안 난다. 어쨌뜬 DMA든 뭐든 멤카피 IO 때문에 코어가 놀았던 것 같다.
블로그 뒤지면 나오겠지만 구글에서 쓴 인터리빙 아호코라식 논문을 구현한 코드도 존재한다. C로 구현되어 있는데 이해하지 못했다. 가져다 쓴 적은 있다.
어찌어찌하여 이리저리 비교를 했었다. rg라는 rust grep 이 있다. 그냥은 빠른데 사전이 커지면 느리다. 아호코라식을 쓰지 않은 것이다. grep은 사전이 커져도 그리 느려지지 않는다. 실버서처는 기억이 안 난다. AVX2-SIMD를 이용하여 문자열 검색을 단순하게 빠르게 구현했을 때 rg와 큰 차이가 나지 않았다. 그 보다는 GPU를 쓰는 쪽이 수십배 빠르다. GPU가 있다면.
이 쪽으로 심화연구 좀 해서 제주도에 논문 발표 핑계로 유급 휴가나 얻어볼까 뚝딱뚝딱 하던 시절이 있었다. 지금은 이거 그냥 가져다 쓰는 참이다.
에혀.